<!DOCTYPE html>
<html class="client-nojs vector-feature-night-mode-disabled vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-sticky-header-enabled" lang="en" dir="ltr"><head>
<meta charset="UTF-8">
<title>Auction algorithm</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="canonical" href="https://en.wikipedia.org/wiki/Auction_algorithm"> <link href="./mw/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/user.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link rel="stylesheet" type="text/css" href="./mw/site.styles.css">
<link rel="stylesheet" type="text/css" href="./mw/noscript.css">
<link rel="stylesheet" type="text/css" href="./footer.css">
<link rel="stylesheet" type="text/css" href="./vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Auction_algorithm rootpage-Auction_algorithm skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading">
<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Auction algorithm</span></span>
</h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><style data-mw-deduplicate="TemplateStyles:r1236090951">
/* start https://en.wikipedia.org/ */
.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}
/* end https://en.wikipedia.org/ */
</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="The_Algorithm_Auction" title="The Algorithm Auction">The Algorithm Auction</a>.</div>
<style data-mw-deduplicate="TemplateStyles:r1129693374">
/* start https://en.wikipedia.org/ */
.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}
/* end https://en.wikipedia.org/ */
</style><style data-mw-deduplicate="TemplateStyles:r1126788409">
/* start https://en.wikipedia.org/ */
.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}
/* end https://en.wikipedia.org/ */
</style><style data-mw-deduplicate="TemplateStyles:r1246091330">
/* start https://en.wikipedia.org/ */
.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}
/* end https://en.wikipedia.org/ */
</style><table class="sidebar nomobile nowraplinks plainlist"><tbody><tr><td class="sidebar-pretitle">Part of a series on</td></tr><tr><th class="sidebar-title-with-pretitle"><a href="Auction" title="Auction">Auctions</a></th></tr><tr><td class="sidebar-image"><span class="notpageimage" typeof="mw:File"></span></td></tr><tr><th class="sidebar-heading" style="background:#ddddff;">
<a href="Auction#Types" title="Auction">Types</a></th></tr><tr><td class="sidebar-content">
<div class="hlist">
<ul><li><a href="All-pay_auction" title="All-pay auction">All-pay</a>
<ul><li><a href="Chinese_auction" title="Chinese auction">Chinese</a></li>
<li><a href="Bidding_fee_auction" title="Bidding fee auction">Bidding fee</a></li>
<li><a href="Dollar_auction" title="Dollar auction">Dollar</a></li></ul></li>
<li><a href="Amsterdam_auction" class="mw-redirect" title="Amsterdam auction">Amsterdam</a></li>
<li><a href="Anglo-Dutch_auction" class="mw-redirect" title="Anglo-Dutch auction">Anglo-Dutch</a></li>
<li><a href="Auction#Participants" title="Auction">Barter double</a></li>
<li><a href="Best/not_best_auction" class="mw-redirect" title="Best/not best auction">Best/not best</a></li>
<li><a href="Brazilian_auction" title="Brazilian auction">Brazilian</a></li>
<li><a href="Calcutta_auction" title="Calcutta auction">Calcutta</a></li>
<li><a href="Candle_auction" title="Candle auction">Candle</a></li>
<li><a href="Tacit_collusion#Tacit_collusion_in_auctions" title="Tacit collusion">Click-box bidding</a></li>
<li><a href="Combinatorial_auction" title="Combinatorial auction">Combinatorial</a></li>
<li><a href="Common_value_auction" title="Common value auction">Common value</a></li>
<li><a href="Deferred-acceptance_auction" title="Deferred-acceptance auction">Deferred-acceptance</a></li>
<li><a href="Discriminatory_price_auction" class="mw-redirect" title="Discriminatory price auction">Discriminatory price</a></li>
<li><a href="Double_auction" title="Double auction">Double</a></li>
<li><a href="Dutch_auction" title="Dutch auction">Dutch</a></li>
<li><a href="English_auction" title="English auction">English</a></li>
<li><a href="Forward_auction" title="Forward auction">Forward</a></li>
<li><a href="French_auction" title="French auction">French</a></li>
<li><a href="Generalized_first-price_auction" title="Generalized first-price auction">Generalized first-price</a></li>
<li><a href="Generalized_second-price_auction" title="Generalized second-price auction">Generalized second-price</a></li>
<li><a href="Japanese_auction" title="Japanese auction">Japanese</a></li>
<li><a href="Knapsack_auction" title="Knapsack auction">Knapsack</a></li>
<li><a href="Multi-attribute_auction" title="Multi-attribute auction">Multi-attribute</a></li>
<li><a href="Multiunit_auction" title="Multiunit auction">Multiunit</a></li>
<li><a href="No-reserve_auction" title="No-reserve auction">No-reserve</a></li>
<li><a href="Rank_auction" class="mw-redirect" title="Rank auction">Rank</a></li>
<li><a href="Reverse_auction" title="Reverse auction">Reverse</a></li>
<li><a href="Scottish_auction" class="mw-redirect" title="Scottish auction">Scottish</a></li>
<li><a href="First-price_sealed-bid_auction" title="First-price sealed-bid auction">Sealed first-price</a></li>
<li><a href="Simultaneous_ascending_auction" class="mw-redirect" title="Simultaneous ascending auction">Simultaneous ascending</a></li>
<li><a href="Single-price_auction" title="Single-price auction">Single-price</a></li>
<li><a href="Traffic-light_auction" class="mw-redirect" title="Traffic-light auction">Traffic light</a></li>
<li><a href="Uniform_price_auction" class="mw-redirect" title="Uniform price auction">Uniform price</a></li>
<li><a href="Unique_bid_auction" title="Unique bid auction">Unique bid</a></li>
<li><a href="Present_value_of_revenues_auction" title="Present value of revenues auction">Value of revenues</a></li>
<li><a href="Vickrey_auction" title="Vickrey auction">Vickrey</a></li>
<li><a href="Vickrey%E2%80%93Clarke%E2%80%93Groves_auction" title="Vickrey–Clarke–Groves auction">Vickrey–Clarke–Groves</a></li>
<li><a href="Walrasian_auction" title="Walrasian auction">Walrasian</a></li>
<li><a href="Yankee_auction" class="mw-redirect" title="Yankee auction">Yankee</a></li></ul>
</div></td>
</tr><tr><th class="sidebar-heading" style="background:#ddddff;">
<a href="Bidding" title="Bidding">Bidding</a></th></tr><tr><td class="sidebar-content">
<div class="hlist">
<ul><li><a href="Bid_shading" title="Bid shading">Shading</a></li>
<li><a href="Calor_licitantis" title="Calor licitantis">Calor licitantis</a></li>
<li><a href="Auction_cancellation_hunter" title="Auction cancellation hunter">Cancellation hunt</a></li>
<li><a href="Jump_bidding" title="Jump bidding">Jump</a></li>
<li><a href="Bid_rigging" title="Bid rigging">Rigging</a></li>
<li><a href="Auction_sniping" title="Auction sniping">Sniping</a></li>
<li><a href="Suicide_bidding" title="Suicide bidding">Suicide</a></li>
<li><a href="Tacit_collusion" title="Tacit collusion">Tacit collusion</a></li></ul>
</div></td>
</tr><tr><th class="sidebar-heading" style="background:#ddddff;">
<a href="Auction#Contexts" title="Auction">Contexts</a></th></tr><tr><td class="sidebar-content">
<div class="hlist">
<ul><li><a href="The_Algorithm_Auction" title="The Algorithm Auction">Algorithms</a></li>
<li><a href="Auto_auction" title="Auto auction">Autos</a></li>
<li><a href="Art_auction" title="Art auction">Art</a></li>
<li><a href="Charity_auction" title="Charity auction">Charity</a></li>
<li><a href="Child_auction" title="Child auction">Children</a></li>
<li><a href="Player_auction" title="Player auction">Players</a></li>
<li><a href="Domain_name_auction" title="Domain name auction">Domain names</a></li>
<li><a href="Aalsmeer_Flower_Auction" title="Aalsmeer Flower Auction">Flowers</a></li>
<li><a href="Term_auction_facility" class="mw-redirect" title="Term auction facility">Loans</a></li>
<li><a href="Mock_auction" title="Mock auction">Scam</a></li>
<li><a href="Scramble_(slave_auction)" title="Scramble (slave auction)">Slaves</a></li>
<li><a href="Spectrum_auction" title="Spectrum auction">Spectrum</a></li>
<li><a href="Philatelic_auction" title="Philatelic auction">Stamps</a></li>
<li><a href="Virginity_auction" title="Virginity auction">Virginity</a></li>
<li><a href="Wine_auction" title="Wine auction">Wine</a></li>
<li><a href="Wife_selling" title="Wife selling">Wives</a></li></ul>
</div></td>
</tr><tr><th class="sidebar-heading" style="background:#ddddff;">
<a href="Auction_theory" title="Auction theory">Theory</a></th></tr><tr><td class="sidebar-content">
<div class="hlist">
<ul><li><a href="Digital_goods_auction" title="Digital goods auction">Digital goods</a></li>
<li><a href="Price_of_anarchy_in_auctions" title="Price of anarchy in auctions">Price of anarchy</a></li>
<li><a href="Revenue_equivalence" title="Revenue equivalence">Revenue equivalence</a></li>
<li><a href="Winner's_curse" title="Winner's curse">Winner's curse</a></li></ul>
</div></td>
</tr><tr><th class="sidebar-heading" style="background:#ddddff;">
<a href="Online_auction" title="Online auction">Online</a></th></tr><tr><td class="sidebar-content">
<div class="hlist">
<ul><li><a href="Ebidding" title="Ebidding">Ebidding</a></li>
<li><a href="Private_electronic_market" title="Private electronic market">Private electronic market</a></li>
<li><a href="Auction_software" title="Auction software">Software</a></li></ul>
</div></td>
</tr><tr><td class="sidebar-navbar"><style data-mw-deduplicate="TemplateStyles:r1239400231">
/* start https://en.wikipedia.org/ */
.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}
/* end https://en.wikipedia.org/ */
</style></td></tr></tbody></table>
<p>The term "<b>auction algorithm</b>"<sup id="cite_ref-Bert79_1-0" class="reference"><a href="#cite_note-Bert79-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> applies to several variations of a <a href="Optimization_(mathematics)" class="mw-redirect" title="Optimization (mathematics)">combinatorial optimization</a> <a href="Algorithm" title="Algorithm">algorithm</a> which solves <a href="Assignment_problem" title="Assignment problem">assignment problems</a>, and network optimization problems with linear and convex/nonlinear cost. An <i>auction algorithm</i> has been used in a business setting to determine the best prices on a set of products offered to multiple buyers. It is an iterative procedure, so the name "auction algorithm" is related to a sales <a href="Auction" title="Auction">auction</a>, where multiple bids are compared to determine the best offer, with the final sales going to the highest bidders.
</p><p>The original form of the auction algorithm is an iterative method to find the optimal prices and an assignment that maximizes the net benefit in a <a href="Bipartite_graph" title="Bipartite graph">bipartite graph</a>, the <i><a href="Maximum_weight_matching" title="Maximum weight matching">maximum weight matching</a> problem</i> (MWM).<sup id="cite_ref-GBooksH_2-0" class="reference"><a href="#cite_note-GBooksH-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>
This algorithm was first proposed by <a href="Dimitri_Bertsekas" title="Dimitri Bertsekas">Dimitri Bertsekas</a> in 1979.
</p><p>The ideas of the auction algorithm and ε-scaling<sup id="cite_ref-Bert79_1-1" class="reference"><a href="#cite_note-Bert79-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> are also central in preflow-push algorithms for single commodity linear network flow problems. In fact the preflow-push algorithm for max-flow can be derived by applying the original 1979 auction algorithm to the max flow problem after reformulation as an assignment problem. Moreover, the preflow-push algorithm for the linear minimum cost flow problem is mathematically equivalent to the ε-relaxation method, which is obtained by applying the original auction algorithm after the problem is reformulated as an equivalent assignment problem.<sup id="cite_ref-Bert86_4-0" class="reference"><a href="#cite_note-Bert86-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>
</p><p>A later variation of the auction algorithm that solves <a href="Shortest_path_problem" title="Shortest path problem">shortest path problems</a> was introduced by Bertsekas in 1991.<sup id="cite_ref-Bert91_5-0" class="reference"><a href="#cite_note-Bert91-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>
It is a simple algorithm for finding shortest paths in a <a href="Directed_graph" title="Directed graph">directed graph</a>. In the single origin/single destination case, the auction algorithm maintains a single path starting at the origin, which is then extended or contracted by a single node at each iteration. Simultaneously, at most one dual variable will be adjusted at each iteration, in order to either improve or maintain the value of a dual function. In the case of multiple origins, the auction algorithm is well-suited for parallel computation.<sup id="cite_ref-Bert91_5-1" class="reference"><a href="#cite_note-Bert91-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> The algorithm is closely related to auction algorithms for other network flow problems.<sup id="cite_ref-Bert91_5-2" class="reference"><a href="#cite_note-Bert91-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> According to computational experiments, the auction algorithm is generally inferior to other state-of-the-art algorithms for the all destinations shortest path problem, but is very fast for problems with few destinations (substantially more than one and substantially less than the total number of nodes); see the article by Bertsekas, Pallottino, and Scutella, <a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01302891">Polynomial Auction Algorithms for Shortest Paths</a>.
</p><p>Auction algorithms for shortest hyperpath problems have been defined by De Leone and Pretolani in 1998. This is also a parallel auction algorithm for weighted bipartite matching, described by E. Jason Riedy in 2004.<sup id="cite_ref-BerkPA_6-0" class="reference"><a href="#cite_note-BerkPA-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>
</p>
<meta property="mw:PageProp/toc">
<div class="mw-heading mw-heading2"><h2 id="Comparisons">Comparisons</h2></div>
<p>The (sequential) auction algorithms for the shortest path problem have been the subject of experiments which have been reported in technical papers.<sup id="cite_ref-DTUauc_7-0" class="reference"><a href="#cite_note-DTUauc-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> Experiments clearly show that the auction algorithm is inferior to the state-of-the-art shortest-path algorithms for finding the optimal solution of single-origin to all-destinations problems.<sup id="cite_ref-DTUauc_7-1" class="reference"><a href="#cite_note-DTUauc-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>
</p><p>Although with the auction algorithm the total benefit is <a href="Monotonic_function" title="Monotonic function">monotonically increasing</a> with each iteration, in the <i><a href="Hungarian_algorithm" title="Hungarian algorithm">Hungarian algorithm</a></i> (from Kuhn, 1955; Munkres, 1957) the total benefit strictly increases with each iteration.
</p><p>The auction algorithm of Bertsekas for finding shortest paths within a directed graph is reputed to perform very well on random graphs and on problems with few destinations.<sup id="cite_ref-Bert91_5-3" class="reference"><a href="#cite_note-Bert91-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>
</p>
<div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2></div>
<ul><li><a href="Hungarian_algorithm" title="Hungarian algorithm">Hungarian algorithm</a></li></ul>
<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>
<div class="mw-references-wrap"><ol class="references">
<li id="cite_note-Bert79-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-Bert79_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Bert79_1-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><a href="Dimitri_P._Bertsekas" class="mw-redirect" title="Dimitri P. Bertsekas">Dimitri P. Bertsekas</a>. "A distributed algorithm for the assignment problem", <a rel="nofollow" class="external text" href="https://www.mit.edu/~dimitrib/Orig_Auction.pdf">original paper, 1979</a>.</span>
</li>
<li id="cite_note-GBooksH-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-GBooksH_2-0">^</a></b></span> <span class="reference-text"><a href="Mauricio_Resende" title="Mauricio Resende">M.G. Resende</a>, P.M. Pardalos. "Handbook of optimization in telecommunications", <a rel="nofollow" class="external text" href="https://books.google.com/books?id=fp7N4Pk6TG4C,">2006</a></span>
</li>
<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">M. Bayati, D. Shah, M. Sharma. "A Simpler Max-Product Maximum Weight Matching Algorithm and the Auction Algorithm", 2006, webpage PDF: <a rel="nofollow" class="external text" href="https://www.mit.edu/~devavrat/bpmwm2.pdf">MIT-bpmwm-PDF</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170921211210/http://www.mit.edu/%7Edevavrat/bpmwm2.pdf">Archived</a> 2017-09-21 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a>.</span>
</li>
<li id="cite_note-Bert86-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-Bert86_4-0">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">
/* start https://en.wikipedia.org/ */
.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}
/* end https://en.wikipedia.org/ */
</style><cite id="CITEREFBertsekas1986" class="citation conference cs1"><a href="Dimitri_Bertsekas" title="Dimitri Bertsekas">Bertsekas, Dimitri</a> (December 1986). "Distributed relaxation methods for linear network flow problems". <i>1986 25th IEEE Conference on Decision and Control</i>. IEEE. pp. <span class="nowrap">2101–</span>2106. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Fcdc.1986.267433">10.1109/cdc.1986.267433</a>.</cite></span>
</li>
<li id="cite_note-Bert91-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-Bert91_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Bert91_5-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-Bert91_5-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-Bert91_5-3"><sup><i><b>d</b></i></sup></a></span> <span class="reference-text">
Dimitri P. Bertsekas. "An auction algorithm for shortest paths", <i>SIAM Journal on Optimization</i>, 1:425—447, 1991,<a rel="nofollow" class="external text" href="http://citeseer.ist.psu.edu/bertsekas91auction.html">PSU-bertsekas91auction</a></span>
</li>
<li id="cite_note-BerkPA-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-BerkPA_6-0">^</a></b></span> <span class="reference-text">"The Parallel Auction Algorithm for Weighted Bipartite Matching", E. Jason Riedy, UC Berkeley, February 2004, <a rel="nofollow" class="external autonumber" href="http://jriedy.users.sonic.net/resume/material/pp04.pdf">[1]</a>.</span>
</li>
<li id="cite_note-DTUauc-7"><span class="mw-cite-backlink">^ <a href="#cite_ref-DTUauc_7-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-DTUauc_7-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFLarsenPedersen1999" class="citation journal cs1">Larsen, Jesper; Pedersen, Ib (1999). <a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=642163">"Experiments with the auction algorithm for the shortest path problem"</a>. <i>Nordic Journal of Computing</i>. <b>6</b> (4): <span class="nowrap">403–</span>42. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1236-6064">1236-6064</a>.</cite>, see also <a rel="nofollow" class="external text" href="http://www.diku.dk/OLD/publikationer/tekniske.rapporter/rapporter/97-07.pdf">A note on the practical performance of the auction algorithm for the shortest path</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110605004126/http://www.diku.dk/OLD/publikationer/tekniske.rapporter/rapporter/97-07.pdf">Archived</a> 2011-06-05 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a> (1997) by the first author.</span>
</li>
</ol></div>
<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>
<ul><li>Dimitri P. Bertsekas. "Linear Network Optimization", MIT Press, 1991, <a rel="nofollow" class="external text" href="http://web.mit.edu/dimitrib/www/net.html">on-line</a>.</li>
<li>Dimitri P. Bertsekas. "Network Optimization: Continuous and Discrete Models", <a rel="nofollow" class="external text" href="http://www.athenasc.com/netbook.html">Athena Scientific, 1998</a>.</li>
<li>Dimitri P. Bertsekas. "An auction algorithm for shortest paths", <i>SIAM Journal on Optimization</i>, 1:425—447, 1991, webpage: <a rel="nofollow" class="external text" href="http://citeseer.ist.psu.edu/bertsekas91auction.html">PSU-bertsekas91auction</a>.</li>
<li>D.P. Bertsekas, S. Pallottino, M. G. Scutella. "Polynomial Auction Algorithms for Shortest Paths," <a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01302891">Computational Optimization and Applications</a>, Vol. 4, 1995, pp. 99-125.</li>
<li>Implementation of Bertsekas' Auction algorithm in Matlab by Florian Bernard, webpage: <a rel="nofollow" class="external text" href="http://de.mathworks.com/matlabcentral/fileexchange/48448-fast-linear-assignment-problem-using-auction-algorithm--mex-">Matlab File Exchange</a>.</li></ul></div><!--htdig_noindex--><div><div class="zim-footer">
This article is issued from <a class="external text" title="Last edited on 2024-09-14" href="https://en.wikipedia.org/wiki/?title=Auction_algorithm&oldid=1245755934">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
</body></html>